package Experiment2;

public class Back4TSP {

    // 表示没有边的权重
    int NoEdge = -1;
    // 表示最大可能的权重值
    int bigInt = Integer.MAX_VALUE;
    // 邻接矩阵，用于存储城市之间的距离
    int[][] a;
    // 当前路径的总权重
    int cc = 0;
    // 当前找到的最优路径的总权重
    int bestc = bigInt;
    // 当前路径的顶点顺序
    int[] x;
    // 最优路径的顶点顺序
    int[] bestx;
    // 顶点的数量
    int n = 0;

    /**
     * 回溯算法的递归函数，用于求解TSP问题。
     *
     * @param i 当前回溯到的顶点索引
     */
    private void backtrack(int i) {
        if (i > n) {
            // 当回溯到所有顶点后，更新最优路径和最小权重
            bestc = cc;
            bestx = x;
        } else {
            // 当回溯到的顶点数量小于顶点总数时，继续回溯
            for (int j = i; j <= n; j++) {
                // 交换当前顶点和另一个顶点的位置
                swap(x[i], x[j]);
                if (check(i)) {
                    // 如果交换后可以继续回溯，则进行下一步
                    if (i < n && cc + a[x[i - 1]][x[i]] < bestc) {
                        // 更新当前路径的权重
                        cc += a[x[i - 1]][x[i]];
                        // 继续回溯到下一个顶点
                        backtrack(i + 1);
                        // 回溯后恢复当前路径的权重
                        cc -= a[x[i - 1]][x[i]];
                    }
                    // 如果当前顶点是最后一个，需要考虑回到起点的路径
                    if (i == n && cc + a[x[i - 1]][x[i]] < bestc) {
                        // 更新当前路径的权重，包括回到起点的边
                        cc += (a[x[i - 1]][x[i]] + a[x[i]][1]);
                        // 继续回溯到下一个顶点
                        backtrack(i + 1);
                        // 回溯后恢复当前路径的权重
                        cc -= (a[x[i - 1]][x[i]] + a[x[i]][1]);
                    }
                }
                // 交换回原来的位置，以便尝试其他顶点
                swap(x[i], x[j]);
            }
        }
    }

    /**
     * 交换数组中两个位置的元素。
     *
     * @param i 第一个元素的位置
     * @param j 第二个元素的位置
     */
    private void swap(int i, int j) {
        int temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    }

    /**
     * 检查当前位置是否可以继续回溯。
     *
     * @param pos 当前检查的顶点索引
     * @return 如果可以继续回溯，则返回true；否则返回false
     */
    public boolean check(int pos) {
        if (pos < 2) return true;
        if (pos < n && a[x[pos - 1]][x[pos]] != NoEdge) return true;
        if (pos == n && a[x[pos - 1]][x[pos]] != NoEdge && a[x[pos]][1] != NoEdge) return true;
        return false;
    }

    /**
     * 使用回溯算法求解TSP问题。
     *
     * @param b 邻接矩阵
     * @param num 顶点的数量
     */
    public void backtrack4TSP(int[][] b, int num) {
        n = num;
        x = new int[n + 1];
        for (int i = 0; i <= n; i++)
            x[i] = i;
        bestx = new int[n + 1];
        a = b;
        backtrack(2);
    }

    
}